package com.peng.leetcode.unionFind;

import java.util.*;

/**
 * MinimumEffortPath
 * <p>
 * 1631. 最小体力消耗路径
 *
 * @author: lupeng6
 * @create: 2021/1/20 15:50
 */
public class MinimumEffortPath {

    public static void main(String[] args) {
//        int[][] heights = {{1, 2, 3}, {3, 8, 4}, {5, 3, 5}};
//        int[][] heights = {{4, 3, 4, 10, 5, 5, 9, 2}, {10, 8, 2, 10, 9, 7, 5, 6}, {5, 8, 10, 10, 10, 7, 4, 2}, {5, 1, 3, 1, 1, 3, 1, 9}, {6, 4, 10, 6, 10, 9, 4, 6}};
//        System.out.println(new MinimumEffortPath().minimumEffortPath(heights));
        LinkedHashMap<String, String> map = new LinkedHashMap<>();
        map.put("1", "1");
        map.remove("1");
        map.put("2", "2");
        map.get("2");
        map.put("3", "3");

    }

    public int minimumEffortPath(int[][] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int rows = heights.length;
        int cols = heights[0].length;
        List<Step> costs = new ArrayList<>();
        UnionFind unionFind = new UnionFind();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int newX = i + 1;
                int newY = j + 1;
                if (newX > 0 && newX < rows) {
                    int cost = Math.abs(heights[i][j] - heights[newX][j]);
                    costs.add(new Step(i * cols + j, newX * cols + j, cost));
                }
                if (newY > 0 && newY < cols) {
                    int cost = Math.abs(heights[i][j] - heights[i][newY]);
                    costs.add(new Step(i * cols + j, i * cols + newY, cost));
                }
            }
        }

        Collections.sort(costs);
        for (Step step : costs) {
            unionFind.union(step.vertexA, step.vertexB);
            if (unionFind.find(0) == unionFind.find(rows * cols - 1)) {
                return step.cost;
            }
        }
        return 0;
    }

    static class UnionFind {
        private Map<Integer, Integer> parent = new HashMap<>();

        public int find(int x) {
            parent.putIfAbsent(x, x);
            while (parent.get(x) != x) {
                x = parent.get(x);
            }
            return x;
        }

        public void union(int x, int y) {
            int xroot = find(x);
            int yroot = find(y);
            if (xroot != yroot) {
                parent.put(xroot, yroot);
            }
        }
    }

    static class Step implements Comparable<Step> {
        int vertexA;

        int vertexB;

        int cost;

        public Step(int vertexA, int vertexB, int cost) {
            this.vertexA = vertexA;
            this.vertexB = vertexB;
            this.cost = cost;
        }

        @Override
        public int compareTo(Step o) {
            return Integer.compare(cost, o.cost);
        }

        @Override
        public String toString() {
            return "vertexA:" + vertexA + " vertexB:" + vertexB + " cost:" + cost;
        }
    }
}
